/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/strobogrammatic-number-ii
   @Language: C++
   @Datetime: 19-04-19 11:02
   */

class Solution {
	vector<vector<char> > mirrors={{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
	void build(int n, int pos, string &str, vector<string> &vs){		
		if(pos>(n>>1)) return;
		if((n&1)==0 && (pos<<1)==n){
			if(str[0]!='0') vs.push_back(str);
			return;
		}
		if((n&1) && (pos<<1)==n-1){
			if(str[0]!='0' || n==1){
				str[pos]='0';
				vs.push_back(str);
				str[pos]='1';
				vs.push_back(str);
				str[pos]='8';
				vs.push_back(str);
			}
			return;
		}
		for(int i=0; i<mirrors.size(); ++i){
			str[pos]=mirrors[i][0];
			str[n-pos-1]=mirrors[i][1];
			build(n,pos+1,str,vs);
		}
	}
public:
	/**
	 * @param num: a string
	 * @return: true if a number is strobogrammatic or false
	 */
	vector<string> findStrobogrammatic(int n) {
		// write your code here
		vector<string> vs;
		if(n<1) return {""};
		string str(n,'0');
		build(n,0,str,vs);
		return vs;
	}
};
